package 每日一题;

import javafx.util.Pair;

import java.util.*;

public class No697数组的度 {

    /**
     * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
     * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     *
     * 示例 1：
     * 输入：[1, 2, 2, 3, 1]
     * 输出：2
     * 解释：
     * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
     * 连续子数组里面拥有相同度的有如下所示:
     * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     * 最短连续子数组[2, 2]的长度为2，所以返回2.
     * 示例 2：
     * 输入：[1,2,2,3,1,4,2]
     * 输出：6
     *
     * 提示：
     * nums.length 在1到 50,000 区间范围内。
     * nums[i] 是一个在 0 到 49,999 范围内的整数。
     */

    //下面自己写的; 官方解法:使用Map<Integet,new int[]{count,left,right}>第一次遍历记录,第二次遍历Map。 复杂度O(2N)
    public int findShortestSubArray(int[] nums) {

        if(nums.length<1){
            return 0;
        }

        Map<Integer,Pair<Integer,Integer>> map=new HashMap<>();
        Map<Integer,Integer> countMap=new HashMap<>();
        Set<Integer> set=new HashSet<>();
        int maxCount=0;

        for (int i = 0; i < nums.length; i++) {
            Pair<Integer, Integer> pair = map.get(nums[i]);
            if(pair==null){
                map.put(nums[i],new Pair<>(i,i));
            }else{
                //更新右
                map.put(nums[i],new Pair<>(pair.getKey(),i));
            }
            //维护count
            Integer count = countMap.getOrDefault(nums[i], 0);
            countMap.put(nums[i],count+1);
            //维护最大count和最大count的集合
            if(maxCount<count+1){
                set.clear();
                set.add(nums[i]);
                maxCount=count+1;
            }else if(maxCount==count+1){
                set.add(nums[i]);
            }
        }

        int result=50000;

        for (Integer num : set) {
            Pair<Integer, Integer> pair = map.get(num);
            result=Math.min(result,pair.getValue()-pair.getKey());
        }

        return result+1;
    }

    public static void main(String[] args) {
        No697数组的度 n=new No697数组的度();
        int[] arr={1};
        int result = n.findShortestSubArray(arr);
        System.out.println(result);
    }

}
